/**
 * @file 093.最长斐波那契数列.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-11-17
 * 
 * @copyright Copyright (c) 2021
 * 
 * 难
 * 
 */

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;

class Solution
{
public:
    int lenLongestFibSubseq(vector<int> &arr)
    {
        // 用map存下(i, j)
        // 当arr[i]+arr[j]==arr[k]时，(i, j)->(j, k)才是连通的
        // dp[i][j] 表示arr[i],arr[j]结尾的最长斐波那契数列长度
        // dp[i][j]=max(dp[k][i] + 1) 满足 k<i<j 且 arr[k]=arr[j]-arr[i]
        int n = arr.size();
        unordered_map<int, int> index;
        for (int i = 0; i < n; ++i) {
            index[arr[i]] = i;
        }
        vector<vector<int>> dp(n, vector<int>(n, 2));
        int res = 0;
        for (int j = 0; j < n; ++j) {
            for (int i = j - 1; i >= 0; --i) {
                int distance = arr[j] - arr[i];
                if (index.count(distance)) {
                    int k = index[distance];
                    if (k < i) {
                        dp[i][j] = max(dp[i][j], dp[k][i] + 1);
                    }
                }
                res = max(res, dp[i][j]);
            }
        }
        return res < 3 ? 0 : res;
    }
};

int main()
{
    vector<int> arr1 = {1, 2, 3, 4, 5, 6, 7, 8};
    vector<int> arr2 = {1, 3, 7, 11, 12, 14, 18};
    cout << Solution().lenLongestFibSubseq(arr1) << endl; // 5
    cout << Solution().lenLongestFibSubseq(arr2) << endl; // 3
    return 0;
}